package lt.liepasoft.sudoku;

public class SudokuSolver {
	
	private final static int MAX_SOLVING_TIME = 5000; //10 seconds 
		
	private SudokuTable table;
	private boolean solved;
	private boolean unsolveable;
	private long startTime;
	
	public SudokuSolver() {
		solved = false;
		startTime = 0;
		unsolveable = false;
	}
	
	public boolean solveSudoku(SudokuTable table){
		this.table = table;
		solved = false;
		unsolveable = false;
		startTime = 0;
		//check if solvable
		if (!isSolveable(table))
			return false;
		
		
		//try to solve
		startTime = System.currentTimeMillis();
		solveSudoku();
		
		if (unsolveable)
			return false;
		
		return true;
	}
	
    private void solveSudoku(){
        if (isSolved(table)){
            this.solved = true;            
            return;
        } else if (System.currentTimeMillis() - startTime > MAX_SOLVING_TIME){
        	this.unsolveable = true;
        } else {        	
        	if (unsolveable)
        		return;
            Point coord;
            if ((coord = getFirstEmptyCell(table))==null)
            	return;                
            int[] possiblies = table.possibleInputs(coord.x, coord.y);
            //starts the recursion
            for (int i=0; i<possiblies.length; i++){
                if (!this.solved){ //need to know when close the recursion
                    table.setCell(coord.x, coord.y, possiblies[i]);
                    solveSudoku();
                    if (this.solved || this.unsolveable)
                        return;
                    
                    table.setCell(coord.x, coord.y, 0);
                } else 
                	return;
            }
        }
    }	
	
	private boolean isSolveable(SudokuTable table){
		for (int x=0; x<SudokuTable.TABLE_SIZE; x++){
			for (int y=0; y<SudokuTable.TABLE_SIZE; y++){
				int[] possiblies = table.possibleInputs(x, y);
				if (possiblies != null && possiblies.length==0)
					return !(unsolveable=true);				
			}
		}
		return true;
	}
	
    private boolean isSolved(SudokuTable table){
        if (solved) return true;
        
        //check if in table are any empty cells
        //if so, then return false
        for (int x=0; x<9; x++)
            for (int y=0; y<9; y++)
                if (table.isCellEmpty(x, y)) return false;
        
        //check if all rows, cols and boxes entries sum value are equal to 45   
        for (int i=0; i<9; i++) {
            if (SudokuUtils.sumUpArray(table.getRow(i))!=45) return false;
            if (SudokuUtils.sumUpArray(table.getCol(i))!=45) return false;
            if (SudokuUtils.sumUpArray(table.getBox(i))!=45) return false;
        }        
        
        return (solved = true);
    }
    
    private Point getFirstEmptyCell(SudokuTable table){	   
	    for (int y=0; y<9; y++)
	        for (int x=0; x<9; x++)
	            if (table.isCellEmpty(x, y)){
	                return new Point(x, y);
	            }
	    return null;
    }    
}
